{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #All Divisions With the Highest Score of a Binary Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScoreIndices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分组得分最高的所有下标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二进制数组 <code>nums</code> ，数组长度为 <code>n</code> 。<code>nums</code> 可以按下标 <code>i</code>（ <code>0 &lt;= i &lt;= n</code> ）拆分成两个数组（可能为空）：<code>nums<sub>left</sub></code> 和 <code>nums<sub>right</sub></code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums<sub>left</sub></code> 包含 <code>nums</code> 中从下标 <code>0</code> 到 <code>i - 1</code> 的所有元素<strong>（包括 </strong><code>0</code><strong> 和 </strong><code>i - 1</code><strong> ）</strong>，而 <code>nums<sub>right</sub></code> 包含 <code>nums</code> 中从下标 <code>i</code> 到 <code>n - 1</code> 的所有元素<strong>（包括 </strong><code>i</code><strong> 和 </strong><code>n - 1</code><strong> ）。</strong></li>\n",
    "\t<li>如果 <code>i == 0</code> ，<code>nums<sub>left</sub></code> 为 <strong>空</strong> ，而 <code>nums<sub>right</sub></code> 将包含 <code>nums</code> 中的所有元素。</li>\n",
    "\t<li>如果 <code>i == n</code> ，<code>nums<sub>left</sub></code> 将包含 <code>nums</code> 中的所有元素，而 <code>nums<sub>right</sub></code> 为 <strong>空</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>下标 <code>i</code><strong> </strong>的<strong> 分组得分</strong> 为 <code>nums<sub>left</sub></code> 中 <code>0</code> 的个数和 <code>nums<sub>right</sub></code> 中 <code>1</code> 的个数之<strong> 和</strong> 。</p>\n",
    "\n",
    "<p>返回 <strong>分组得分 最高</strong> 的 <strong>所有不同下标</strong> 。你可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,0,1,0]\n",
    "<strong>输出：</strong>[2,4]\n",
    "<strong>解释：</strong>按下标分组\n",
    "- 0 ：nums<sub>left</sub> 为 [] 。nums<sub>right</sub> 为 [0,0,<em><strong>1</strong></em>,0] 。得分为 0 + 1 = 1 。\n",
    "- 1 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>] 。nums<sub>right</sub> 为 [0,<em><strong>1</strong></em>,0] 。得分为 1 + 1 = 2 。\n",
    "- 2 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>,<em><strong>0</strong></em>] 。nums<sub>right</sub> 为 [<em><strong>1</strong></em>,0] 。得分为 2 + 1 = 3 。\n",
    "- 3 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>,<em><strong>0</strong></em>,1] 。nums<sub>right</sub> 为 [0] 。得分为 2 + 0 = 2 。\n",
    "- 4 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>,<em><strong>0</strong></em>,1,<em><strong>0</strong></em>] 。nums<sub>right</sub> 为 [] 。得分为 3 + 0 = 3 。\n",
    "下标 2 和 4 都可以得到最高的分组得分 3 。\n",
    "注意，答案 [4,2] 也被视为正确答案。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,0,0]\n",
    "<strong>输出：</strong>[3]\n",
    "<strong>解释：</strong>按下标分组\n",
    "- 0 ：nums<sub>left</sub> 为 [] 。nums<sub>right</sub> 为 [0,0,0] 。得分为 0 + 0 = 0 。\n",
    "- 1 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>] 。nums<sub>right</sub> 为 [0,0] 。得分为 1 + 0 = 1 。\n",
    "- 2 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>,<em><strong>0</strong></em>] 。nums<sub>right</sub> 为 [0] 。得分为 2 + 0 = 2 。\n",
    "- 3 ：nums<sub>left</sub> 为 [<em><strong>0</strong></em>,<em><strong>0</strong></em>,<em><strong>0</strong></em>] 。nums<sub>right</sub> 为 [] 。得分为 3 + 0 = 3 。\n",
    "只有下标 3 可以得到最高的分组得分 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1]\n",
    "<strong>输出：</strong>[0]\n",
    "<strong>解释：</strong>按下标分组\n",
    "- 0 ：nums<sub>left</sub> 为 [] 。nums<sub>right</sub> 为 [<em><strong>1</strong></em>,<em><strong>1</strong></em>] 。得分为 0 + 2 = 2 。\n",
    "- 1 ：nums<sub>left</sub> 为 [1] 。nums<sub>right</sub> 为 [<em><strong>1</strong></em>] 。得分为 0 + 1 = 1 。\n",
    "- 2 ：nums<sub>left</sub> 为 [1,1] 。nums<sub>right</sub> 为 [] 。得分为 0 + 0 = 0 。\n",
    "只有下标 0 可以得到最高的分组得分 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [all-divisions-with-the-highest-score-of-a-binary-array](https://leetcode.cn/problems/all-divisions-with-the-highest-score-of-a-binary-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [all-divisions-with-the-highest-score-of-a-binary-array](https://leetcode.cn/problems/all-divisions-with-the-highest-score-of-a-binary-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,0,1,0]', '[0,0,0]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        a=b=sum(nums)\n",
    "        ans =[0]\n",
    "        for i,v in enumerate(nums,1):\n",
    "            if v:\n",
    "                a-=1\n",
    "            else:\n",
    "                a+=1\n",
    "                if a>b:\n",
    "                    ans=[i]\n",
    "                    b=a\n",
    "                elif a==b:\n",
    "                    ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        right = nums.count(1)\n",
    "        mx = right\n",
    "        ans = [0]\n",
    "        left = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            left += x ^ 1\n",
    "            right -= x & 1\n",
    "            if left + right == mx:\n",
    "                ans.append(i + 1)\n",
    "            elif left + right > mx:\n",
    "                ans = [i + 1]\n",
    "                mx = left + right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res = [0]\n",
    "        l = 0\n",
    "        r = nums.count(1)\n",
    "        m = l + r\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            if l+r == m:\n",
    "                res.append(i+1)\n",
    "            elif l+r >m:\n",
    "                res = [i+1]\n",
    "                m = l + r \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        maxscore = 0\n",
    "        presum = 0\n",
    "        ret = [0]\n",
    "\n",
    "        for i,num in enumerate(nums) :\n",
    "            if num == 0 :\n",
    "                presum += 1\n",
    "                if presum > maxscore :\n",
    "                    maxscore = presum\n",
    "                    ret = [i+1]\n",
    "                elif presum == maxscore :\n",
    "                    ret.append(i+1)\n",
    "            else :\n",
    "                presum -= 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        best = base = sum(nums)\n",
    "        ans = [0]\n",
    "        for i, j in enumerate(nums):\n",
    "            if j:\n",
    "                base -= 1\n",
    "            else:\n",
    "                base += 1\n",
    "                if base > best:\n",
    "                    best = base\n",
    "                    ans = [i + 1]\n",
    "                elif base == best:\n",
    "                    ans.append(i + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        pres = best = 0\n",
    "        ans = [0]\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                pres += 1\n",
    "                if pres > best:\n",
    "                    best = pres\n",
    "                    ans = [i+1]\n",
    "                elif pres == best:\n",
    "                    ans.append(i+1)\n",
    "            else:\n",
    "                pres -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        # ans 为历史最大值的下标\n",
    "        ans = [0]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "                # best 为历史最大值\n",
    "        presum = best = 0\n",
    "        ans = [0]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i + 1]\n",
    "                elif presum == best:\n",
    "                    ans.append(i + 1)\n",
    "            else:\n",
    "                presum -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        presum, m, ans = 0, -inf, []\n",
    "        for i in range(n+1):\n",
    "            if (res:= presum * 2 - i) > m:\n",
    "                m = res\n",
    "                ans = [i]\n",
    "            elif res == m:\n",
    "                ans.append(i)\n",
    "            if i < n:\n",
    "                presum += nums[i] == 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        mx = score = sum(nums)\n",
    "        ans = [0]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            score += 1 - 2 * nums[i-1]\n",
    "            if score > mx:\n",
    "                mx = score\n",
    "                ans = [i]\n",
    "            elif mx == score:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        presum = best = 0\n",
    "        ans=[0]\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                presum += 1\n",
    "                if presum > best:\n",
    "                    best = presum\n",
    "                    ans = [i+1]\n",
    "                elif presum == best:\n",
    "                    ans. append(i+1)\n",
    "            else :\n",
    "                presum -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        cnt=Counter(nums)\n",
    "        cnt0=cnt[0]\n",
    "        cnt1=cnt[1]\n",
    "        ma=cnt1\n",
    "        cur=cnt1\n",
    "        for x in nums:\n",
    "            if x==0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur-=1\n",
    "            ma=max(ma,cur)\n",
    "        ans=[]\n",
    "        cur=cnt1\n",
    "        if cur==ma:\n",
    "            ans.append(0)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==0:\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur-=1\n",
    "            if cur==ma:\n",
    "                ans.append(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        pres = best = 0\n",
    "        ans = [0]\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                pres += 1\n",
    "                if pres > best:\n",
    "                    best = pres\n",
    "                    ans = [i+1]\n",
    "                elif pres == best:\n",
    "                    ans.append(i+1)\n",
    "            else:\n",
    "                pres -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        presum, m, ans = 0, -inf, []\n",
    "        for i in range(n+1):\n",
    "            if (res:= presum * 2 - i) > m:\n",
    "                m = res\n",
    "                ans = [i]\n",
    "            elif res == m:\n",
    "                ans.append(i)\n",
    "            if i < n:\n",
    "                presum += nums[i] == 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        presum, m, ans = 0, -inf, []\n",
    "        for i in range(n+1):\n",
    "            if (res:= presum * 2 - i) > m:\n",
    "                m = res\n",
    "                ans = [i]\n",
    "            elif res == m:\n",
    "                ans.append(i)\n",
    "            if i < n:\n",
    "                presum += nums[i] == 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res = sum(nums)\n",
    "        l,r = 0,res\n",
    "        for idx,i in enumerate(nums):\n",
    "            if i == 0:\n",
    "                l += 1\n",
    "                res = max(res,l+r)\n",
    "            else:\n",
    "                r -= 1\n",
    "                res = max(res,l+r)\n",
    "        l,r = 0,sum(nums)\n",
    "        Res = []\n",
    "        if r == res:\n",
    "            Res.append(0)\n",
    "        for idx,i in enumerate(nums):\n",
    "            if i == 0:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            if l+r == res:Res.append(idx+1)\n",
    "        return Res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]\n",
    "        s = sum(nums)\n",
    "        mx = s\n",
    "        c0, c1 = 0, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 0:\n",
    "                c0 += 1\n",
    "            else:\n",
    "                c1 += 1\n",
    "            score = c0 + s - c1\n",
    "            #print(f'score = {score}, s = {s}')\n",
    "            if score > mx:\n",
    "                ans = [i + 1]\n",
    "                mx = score\n",
    "            elif score == mx:\n",
    "                ans.append(i + 1)\n",
    "        return ans                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones_total = sum(nums)\n",
    "        ones_cnt = 0\n",
    "        zeros_cnt = 0\n",
    "        score = ones_total\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                zeros_cnt += 1\n",
    "            else:\n",
    "                ones_cnt += 1\n",
    "            if(score < zeros_cnt + ones_total - ones_cnt):\n",
    "                result = [i+1]\n",
    "                score = zeros_cnt + ones_total - ones_cnt\n",
    "            elif(score == zeros_cnt + ones_total - ones_cnt):\n",
    "                result.append(i+1)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        targat=[]\n",
    "        max_score,current_score=0,0\n",
    "        nums_len=len(nums)\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                max_score+=1\n",
    "        targat.append(0)\n",
    "        current_score=max_score\n",
    "        for i in range(1,nums_len+1):\n",
    "            if nums[i-1]==0:\n",
    "                current_score=current_score+1\n",
    "            elif nums[i-1]==1:\n",
    "                current_score=current_score-1\n",
    "\n",
    "            if max_score<current_score:\n",
    "                # print('小于')\n",
    "                # print(i)\n",
    "                targat=[i]\n",
    "                max_score=current_score\n",
    "\n",
    "            elif max_score==current_score:\n",
    "                # print('等于')\n",
    "                # print(i)\n",
    "                targat.append(i)\n",
    "\n",
    "        return targat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones_total = sum(nums)\n",
    "        ones_cnt = 0\n",
    "        zeros_cnt = 0\n",
    "        score = ones_total\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                zeros_cnt += 1\n",
    "            else:\n",
    "                ones_cnt += 1\n",
    "            if(score < zeros_cnt + ones_total - ones_cnt):\n",
    "                result = [i+1]\n",
    "                score = zeros_cnt + ones_total - ones_cnt\n",
    "            elif(score == zeros_cnt + ones_total - ones_cnt):\n",
    "                result.append(i+1)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones_total = sum(nums)\n",
    "        ones_cnt = 0\n",
    "        zeros_cnt = 0\n",
    "        score = ones_total\n",
    "        result = [0]\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 0):\n",
    "                zeros_cnt += 1\n",
    "            else:\n",
    "                ones_cnt += 1\n",
    "            if(score < zeros_cnt + ones_total - ones_cnt):\n",
    "                result = [i+1]\n",
    "                score = zeros_cnt + ones_total - ones_cnt\n",
    "            elif(score == zeros_cnt + ones_total - ones_cnt):\n",
    "                result.append(i+1)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        s = sum(nums)\n",
    "        sl, sr = 0, s\n",
    "        ans = [0]\n",
    "        mx = s\n",
    "        for i, x in enumerate(nums):\n",
    "            sl += x ^ 1\n",
    "            sr -= x\n",
    "            score = sl + sr\n",
    "            if score > mx:\n",
    "                mx = score\n",
    "                ans = [i + 1]\n",
    "            elif score == mx:\n",
    "                ans.append(i + 1)\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res = [0]\n",
    "        l = 0\n",
    "        r = nums.count(1)\n",
    "        m = l + r\n",
    "        for i in range(len(nums)):\n",
    "            print(m)\n",
    "            if nums[i] == 0:\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "            if l+r == m:\n",
    "                res.append(i+1)\n",
    "            elif l+r >m:\n",
    "                res = [i+1]\n",
    "                m = l + r \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*(n+1)\n",
    "        total=sum(nums)\n",
    "        ans[0]=total\n",
    "        count_0,count_1=0,total\n",
    "        for i in range(1,n+1):\n",
    "            if nums[i-1]==0:\n",
    "                count_0+=1\n",
    "            else:\n",
    "                count_1-=1\n",
    "            ans[i]=count_0+count_1\n",
    "        ans[n]=nums.count(0)\n",
    "        cur=max(ans)\n",
    "        return [i for i in range(n+1) if ans[i]==cur]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        right = nums.count(1)\n",
    "        n = len(nums)\n",
    "        ans = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            ans[i] = left+right\n",
    "            if i < n:\n",
    "                if nums[i] == 0:\n",
    "                    left += 1\n",
    "                if nums[i] == 1:\n",
    "                    right -= 1\n",
    "        \n",
    "        maxval = max(ans)\n",
    "        return [i for i, x in enumerate(ans) if x == maxval]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "      n = len(nums)\n",
    "      suffix = [0] * (n + 1)\n",
    "\n",
    "      for i in range(n - 1, -1, -1):\n",
    "        suffix[i] = suffix[i + 1] + (nums[i] == 1)\n",
    "      \n",
    "      ans = []\n",
    "      max_ = float('-inf')\n",
    "\n",
    "      left_sum = 0\n",
    "      for i in range(n + 1):\n",
    "        sum_ = left_sum + suffix[i]\n",
    "        if sum_ > max_:\n",
    "          ans = [i]\n",
    "          max_ = sum_\n",
    "        elif sum_ == max_:\n",
    "          ans.append(i)\n",
    "        \n",
    "        if i == n:\n",
    "          break\n",
    "        \n",
    "        left_sum += nums[i] == 0\n",
    "\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ones = sum(nums)\n",
    "        res = [0] * (n + 1)\n",
    "        base = ones \n",
    "        res[0] = base \n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1]:\n",
    "                base -= 1\n",
    "            else:\n",
    "                base += 1\n",
    "            res[i] = base \n",
    "        mx = max(res)\n",
    "        ans = []\n",
    "        for i in range(n + 1):\n",
    "            if res[i] == mx:\n",
    "                ans.append(i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        right = nums.count(1)\n",
    "        n = len(nums)\n",
    "        ans = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            ans[i] = left+right\n",
    "            if i < n:\n",
    "                if nums[i] == 0:\n",
    "                    left += 1\n",
    "                if nums[i] == 1:\n",
    "                    right -= 1\n",
    "        \n",
    "        maxval = max(ans)\n",
    "        return [i for i, x in enumerate(ans) if x == maxval]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        left=0\n",
    "        right=0\n",
    "        l=len(nums)\n",
    "        for i in range(l):\n",
    "            if nums[i]==1:\n",
    "                right+=1\n",
    "        res.append(left+right)\n",
    "        count=0\n",
    "        while count<l:\n",
    "            if nums[count]==0:\n",
    "                left+=1\n",
    "            if nums[count]==1:\n",
    "                right-=1\n",
    "            res.append(left+right)\n",
    "            count+=1\n",
    "        m=max(res)\n",
    "        ans=[]\n",
    "        for i in range(l+1):\n",
    "            if m==res[i]:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\r\n",
    "        c = collections.Counter(nums)\r\n",
    "        n = len(nums)\r\n",
    "        lf, rt = 0, c[1]\r\n",
    "        ans = [lf + rt]\r\n",
    "        for i in range(n):\r\n",
    "            if nums[i] == 0:\r\n",
    "                lf += 1\r\n",
    "            if nums[i] == 1:\r\n",
    "                rt -= 1\r\n",
    "            ans.append(lf + rt)\r\n",
    "        maxx = max(ans)\r\n",
    "        return [i for i in range(n + 1) if ans[i] == maxx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        sumLeft = 0\n",
    "        sumRight = sum(nums)\n",
    "        scores = []\n",
    "        res = []\n",
    "        mx = 0\n",
    "        for i in range(len(nums)):\n",
    "            scores.append(sumLeft + sumRight)\n",
    "            if scores[i] > mx:\n",
    "                res = [i]\n",
    "                mx = scores[i]\n",
    "            elif scores[i] == mx:\n",
    "                res.append(i)\n",
    "            if nums[i] == 0:\n",
    "                sumLeft += 1\n",
    "            elif nums[i] == 1:\n",
    "                sumRight -= 1\n",
    "        scores.append(sumLeft + sumRight)\n",
    "        if scores[-1] > mx:\n",
    "            res = [len(nums)]\n",
    "        elif scores[-1] == mx:\n",
    "            res.append(len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        sumLeft = 0\n",
    "        sumRight = sum(nums)\n",
    "        scores = []\n",
    "        res = []\n",
    "        mx = 0\n",
    "        for i in range(len(nums) + 1):\n",
    "            scores.append(sumLeft + sumRight)\n",
    "            if scores[i] > mx:\n",
    "                res = [i]\n",
    "                mx = scores[i]\n",
    "            elif scores[i] == mx:\n",
    "                res.append(i)\n",
    "            if i == len(nums): break\n",
    "            if nums[i] == 0:\n",
    "                sumLeft += 1\n",
    "            elif nums[i] == 1:\n",
    "                sumRight -= 1\n",
    "        scores.append(sumLeft + sumRight)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums)\n",
    "        # 0 - N\n",
    "        zero_nums = [0] * (N+1)\n",
    "        one_nums = [0] * (N+1)\n",
    "\n",
    "        for i in range(1,N+1) :\n",
    "            zero_nums[i] = zero_nums[i-1]\n",
    "            if nums[i-1] == 0 :\n",
    "                zero_nums[i] += 1\n",
    "\n",
    "        for i in range(N-1, -1 , -1) :\n",
    "            one_nums[i] = one_nums[i+1]\n",
    "            if nums[i] == 1 :\n",
    "                one_nums[i] += 1\n",
    "        \n",
    "        ret = []\n",
    "        maxscore = -1\n",
    "        for i in range(N+1) :\n",
    "            score = zero_nums[i] + one_nums[i]\n",
    "            if score > maxscore :\n",
    "                maxscore = score\n",
    "                ret = [i]\n",
    "            elif score == maxscore :\n",
    "                ret.append(i)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left_zeros = [0] * (n + 1)\n",
    "        right_ones = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            left_zeros[i + 1] = left_zeros[i] + (1 if nums[i] == 0 else 0)\n",
    "            right_ones[n - i - 1] = right_ones[n - i] + (1 if nums[n - i - 1] == 1 else 0)\n",
    "\n",
    "        max_score = 0\n",
    "        max_score_indices = []\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            score = left_zeros[i] + right_ones[i]\n",
    "            if score > max_score:\n",
    "                max_score = score\n",
    "                max_score_indices = [i]\n",
    "            elif score == max_score:\n",
    "                max_score_indices.append(i)\n",
    "\n",
    "        return max_score_indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            left[i + 1] = left[i] + (nums[i] == 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            right[i] = right[i + 1] + (nums[i] == 1)\n",
    "        cur_max = 0\n",
    "        ans = []\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            res = left[i] + right[i]\n",
    "            if res > cur_max:\n",
    "                cur_max = res\n",
    "                ans = [i]\n",
    "            elif res == cur_max:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        # nums = [0,0,1,0]\n",
    "        prefix = [0] * (len(nums) + 1)\n",
    "        suffix = [0] * (len(nums) + 1)\n",
    "        for i in range(1, len(prefix)):\n",
    "            if nums[i - 1] == 0:\n",
    "                prefix[i] += prefix[i - 1] + 1\n",
    "            else:\n",
    "                prefix[i] = prefix[i - 1]\n",
    "        for i in range(len(suffix) - 2, -1, -1):\n",
    "            if nums[i] == 1:\n",
    "                suffix[i] += suffix[i + 1] + 1\n",
    "            else:\n",
    "                suffix[i] = suffix[i + 1]\n",
    "        res = []\n",
    "        for p, s in zip(prefix, suffix):\n",
    "            res.append(p + s)\n",
    "        maxNum = max(res)\n",
    "        ans = []\n",
    "        for i, v in enumerate(res):\n",
    "            if v == maxNum:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        f = [[0, 0] for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            f[i + 1][0] = f[i][0]\n",
    "            f[i + 1][1] = f[i][1]\n",
    "            f[i + 1][nums[i]] += 1\n",
    "        ret, retlist = f[n][0], [n]\n",
    "        for i in range(n):\n",
    "            if ret == f[i][0] + f[n][1] - f[i][1]:\n",
    "                retlist.append(i)\n",
    "            elif ret < f[i][0] + f[n][1] - f[i][1]:\n",
    "                ret = f[i][0] + f[n][1] - f[i][1]\n",
    "                retlist = [i]\n",
    "        return retlist    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreIndices(self, nums: List[int]) -> List[int]:\n",
    "        score = dict()\n",
    "        postsum = sum(nums)\n",
    "        presum = 0\n",
    "        for i in range(len(nums)):\n",
    "            score[i] = i - presum + postsum\n",
    "            presum += nums[i]\n",
    "            postsum -= nums[i]\n",
    "        score[len(nums)] = len(nums) - presum\n",
    "        target = max(score.values())\n",
    "        return [i for i, j in score.items() if j == target]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
